/*
 * Functions to post process HXD1 IR and some simple optimizations.
 * NOTE: some optimizations have been done while generating IR code,
 * such as evaluating constant expressions.
 */
#include "HIRCode.h"
#include "HXD1.h"
//#include <map>
#include <algorithm>

/*
 * Post processing for HXD1 IR after it is generated. Including:
 * removing the redundant labels;
 * dividing IR code into basic blocks;
 * constructing CFG (control flow graph);
 * doing other optimizations according to `opts.opt_level`;
 * ...
 */
void HIRCode::post_process()
{
	std::vector<HIRFunct>::iterator func;

	for (func = _funct.begin() + _nbuiltin; func != _funct.end(); ++func)
	{
		if (opts.opt_cfg_cleanup)
		{
			func->opt_remove_redundant_labels();
			func->opt_control_flow_graph_cleanup();
		}
		func->divide_basic_blocks();
		func->construct_control_flow_graph();
		func->traverse_control_flow_graph(func->basic_blocks.at(0ul));
		if (opts.opt_str_red)
			func->opt_strength_reduction();
		if (opts.opt_level > 0)
			func->opt_merge_adjacent();
		if (opts.opt_dce)
			func->opt_dead_code_elimination(false);
		/*
		 * After flow equations are solved, DCE can be done again with `true`.
		 * Besides, CSE can also be done with the flag `true`.
		 */
		func->dfa_solve_livevar();
		if (opts.opt_dce)
			// Try to eliminate and solve until no more change
			while (func->opt_dead_code_elimination(true) > 0ul)
				func->dfa_solve_livevar();
		if (opts.opt_cse)
			if (func->opt_common_subexpr_elimination(true) > 0ul)
				// update
				func->dfa_solve_livevar();
		if (opts.opt_gra)
		{
			func->dfa_solve_dominators();
			func->dfa_detect_loops();
			func->dfa_calc_spillcost();
		}
	}
}

/*
 * Replace all "rip" label with "rep" and set their `fassigned`, `lrefered`.
 * "rip" means the first label in mapping, and "rep" is the second.
 * Specifically, for every branch instruction, scan `lpairs`. If a
 * label in the instruction severs as "rip" in `lpairs`, then replace
 * it with the corresponding "rep". After that, set their `fassigned` and `lrefered`.
 * NOTE: if there are two pairs: `{2, 3}` and `{3, 5}`, this function may NOT
 * work well. So, please replace the first one with `{2, 5}` before calling it!
 * Return the number of label references replaced.
 */
static int replace_labels(HIRFunct &func, const std::map<HIRLabel, HIRLabel> &lpairs)
{
	std::map<HIRLabel, HIRLabel>::const_iterator it;
	int r_ymr = 0;
	// scan the instructions
	for (auto &inst : func.ircode)
		if (inst.oper == HIROper::BRc)
		{
			if ((it = lpairs.find(inst.iftrue)) != lpairs.end())
				inst.iftrue = it->second, ++r_ymr;
			if ((it = lpairs.find(inst.iffalse)) != lpairs.end())
				inst.iffalse = it->second, ++r_ymr;
		}
		else if (inst.oper == HIROper::BRu)
		{
			if ((it = lpairs.find(inst.brdest)) != lpairs.end())
				inst.brdest = it->second, ++r_ymr;
		}
	// set `fassigned` and `lrefered`
	for (auto &pair : lpairs)
	{
		auto rip = func.temps.begin() + pair.first;
		auto rep = func.temps.begin() + pair.second;
		if (rip->frefed < rep->frefed)
			rep->frefed = rip->frefed;
		if (rip->lrefed > rep->lrefed)
			rep->lrefed = rip->lrefed;
		rip->fassigned = INVALID_INST_IDX;
		rip->frefed = INVALID_INST_IDX;
		rip->lrefed = INVALID_INST_IDX;
	}
	return r_ymr;
}

/*
 * Scan all instructions and remove redundant labels.
 * If two or more labels are consensus, they will be considered as redundant.
 * Then, the last label will replace the other labels.
 */
int HIRFunct::opt_remove_redundant_labels()
{
	std::map<HIRLabel, HIRLabel> lpairs;
	size_t clf, cll;	// consensus label first/last
	size_t ninst = ircode.size();
	HIRLabel rep;
	int r_ymr = 0;
	
	for (clf = 0ul; clf < ninst; ++clf)
	{
		if (ircode.at(clf).oper == HIROper::LABEL)
		{
			for (cll = clf + 1ul; cll < ninst &&
				(ircode.at(clf).oper == HIROper::EMPTY_LINE
				|| ircode.at(cll).oper == HIROper::LABEL); ++cll)
				;
			while (cll >= ninst || ircode.at(cll).oper != HIROper::LABEL)
				--cll;
			if (cll < clf)
				throw std::logic_error("Failed while removing redundant labels");
			rep = ircode.at(cll).labelno;
			// Now `cll` points to the last inst of the consensus insts
			for (; clf < cll; ++clf)
				if (ircode.at(clf).oper == HIROper::LABEL)
				{
					// map a "rip" to "rep"
					lpairs[ircode.at(clf).labelno] = rep;
					ircode.at(clf).oper = HIROper::EMPTY_LINE;
					++r_ymr;
				}
		}
	}
	replace_labels(*this, lpairs);
	return r_ymr;
}


/*
 * Merge continuous jumps, such as jumping to unconditional jumps.
 */
void HIRFunct::opt_control_flow_graph_cleanup()
{
	uint32_t iidx, ninsts = ircode.size(), next_inst;
	// indexes of branch instructions
	std::vector<uint32_t> brinsts;
	// iterators
	std::vector<uint32_t>::iterator brit, brit_u;
	// branch targets
	std::vector<HIRLabel> brdests;
	bool flag_changed = true;

	/*
	 * Push all indexes of branch instructions
	 * into `brinsts` in order.
	 */
	for (iidx = 0u; iidx < ninsts; ++iidx)
		if (ircode.at(iidx).oper == HIROper::BRc
			|| ircode.at(iidx).oper == HIROper::BRu)
			brinsts.push_back(iidx);
	// iterative algorithm
	while (flag_changed)
	{
		flag_changed = false;
		for (brit = brinsts.begin(); brit != brinsts.end(); ++brit)
		{
			brdests.clear();
			if (ircode.at(*brit).oper == HIROper::BRc)
			{
				brdests.push_back(ircode.at(*brit).iftrue);
				brdests.push_back(ircode.at(*brit).iffalse);
			}
			else if (ircode.at(*brit).oper == HIROper::BRu)
				brdests.push_back(ircode.at(*brit).brdest);
			else
			/*
			 * When "(unconditional) jump to next" is detected,
			 * a `BRu` instruction may be set as `EMPTY_LINE`.
			 * So, we should skip it in the future scanning.
			 */
				continue;
			for (auto brd : brdests)
			{
				// try to find the next instruction of the label
				// flag of the next instruction is `BRu`
				bool flag_jump2jump_found = false;
				// flag of the label is the next of a `BRu`
				bool flag_jump2next_found = false;
				HIRLabel brd2 = INVALID_LABEL;
				// detect (unconditional) jump to next
				if (brdests.size() == 1ul)
				{
					for (next_inst = *brit + 1u; next_inst < ircode.size() &&
						(ircode.at(next_inst).oper == HIROper::EMPTY_LINE
						// skip irrelevant labels, too
						|| (ircode.at(next_inst).oper == HIROper::LABEL
						&& ircode.at(next_inst).labelno != brd)); ++next_inst)
						;	// find the next instruction
					if (next_inst < ircode.size() && temps.at(brd).fassigned == next_inst)
						flag_jump2next_found = true;
				}
				// detect jump to jump
				if (ircode.at(temps.at(brd).fassigned).oper != HIROper::LABEL
					|| ircode.at(temps.at(brd).fassigned).labelno != brd)
					throw std::logic_error(std::to_string(brd) +
						": wrong fassigned: " + std::to_string(temps.at(brd).fassigned));
				for (next_inst = temps.at(brd).fassigned + 1u;
					next_inst < ircode.size() &&
					ircode.at(next_inst).oper == HIROper::EMPTY_LINE; ++next_inst)
					;	// find the next instruction
				if (next_inst < ircode.size() &&
					ircode.at(next_inst).oper == HIROper::BRu)
				{
					flag_jump2jump_found = true;
					brd2 = ircode.at(next_inst).brdest;
				}
				if (!flag_jump2jump_found && !flag_jump2next_found)
					continue;
				flag_changed = true;
				if (flag_jump2jump_found)
				{	// Replace the branch dest!
					ircode.at(*brit).brdests_replace(brd, brd2);
					// Update `f/lrefered` of `brd2`
					if (temps.at(brd2).frefed == INVALID_INST_IDX
						|| temps.at(brd2).frefed > *brit)
						temps.at(brd2).frefed = *brit;
					if (temps.at(brd2).lrefed == INVALID_INST_IDX
						|| temps.at(brd2).lrefed < *brit)
						temps.at(brd2).lrefed = *brit;
				}
				else if (flag_jump2next_found)
					// Remove (unconditional) jump to next
					ircode.at(*brit).oper = HIROper::EMPTY_LINE;
				// Update `f/lrefered` of `brd`
				if (temps.at(brd).frefed == *brit)
				{
					temps.at(brd).frefed = INVALID_INST_IDX;
					for (brit_u = brit; *brit_u <= temps.at(brd).lrefed
						&& brit_u != brinsts.end(); ++brit_u)
						if ((ircode.at(*brit_u).oper == HIROper::BRu
							&& ircode.at(*brit_u).brdest == brd)
							|| (ircode.at(*brit_u).oper == HIROper::BRc
							&& (ircode.at(*brit_u).iftrue == brd
							|| ircode.at(*brit_u).iffalse == brd)))
						{
							temps.at(brd).frefed = *brit_u;
							break;
						}
					if (temps.at(brd).frefed == INVALID_INST_IDX)
						temps.at(brd).lrefed = INVALID_INST_IDX;
				}
				if (temps.at(brd).lrefed == *brit)
				{	// If that happens, `frefered` must be less than `lrefered`!
					brit_u = brit;
					temps.at(brd).lrefed = INVALID_INST_IDX;
					do
						if ((ircode.at(*brit_u).oper == HIROper::BRu
							&& ircode.at(*brit_u).brdest == brd)
							|| (ircode.at(*brit_u).oper == HIROper::BRc
							&& (ircode.at(*brit_u).iftrue == brd
							|| ircode.at(*brit_u).iffalse == brd)))
						{
							temps.at(brd).lrefed = *brit_u;
							break;
						}
					while (*brit_u >= temps.at(brd).frefed &&
						brit_u != brinsts.begin() && (*--brit_u || true));
					if (temps.at(brd).lrefed == INVALID_INST_IDX)
						throw std::logic_error(
							"Failed to update lrefered of" + std::to_string(brd));
				}
				if (temps.at(brd).frefed == INVALID_INST_IDX)
				{	// remove invalid label
					ircode.at(temps.at(brd).fassigned).oper = HIROper::EMPTY_LINE;
					temps.at(brd).fassigned = INVALID_INST_IDX;
				}
			}
		}
	}
}

/*
 * Divide the IR code into basic blocks and return the
 * number of basic blocks.
 * Also discover all local temps.
 */
uint32_t HIRFunct::divide_basic_blocks()
{
	uint32_t iidx, bidx, ninst = ircode.size();
	bool flag_in_bb = false;
	BasicBlock tempbb;
	// index of the last non-empty instruction
	uint32_t last_idx = INVALID_INST_IDX;
	// scan arguments
	HIRTempno ta;
	HIRInst empty_line(HIROper::EMPTY_LINE);

	// Initialize it as `false`
	tempbb.reachable = false;
	// All `ALLOCA` instructions forms the first BB.
	if (nalloca > 0u)
	{
		tempbb.begin = 0u;
		tempbb.end = nalloca - 1u;
	}
	else	// otherwise, set `begin` and `end` invalid.
		tempbb.begin = tempbb.end = INVALID_INST_IDX;
	basic_blocks.push_back(tempbb);
	// Scan the instructions
	for (iidx = nalloca; iidx < ninst; ++iidx)
	{
		auto inst = ircode.begin() + iidx;
		if (inst->oper == HIROper::EMPTY_LINE)
			continue;
		tempbb.begin = iidx;
		tempbb.end = INVALID_INST_IDX;

		if (flag_in_bb)
		{	// already in a BB
			if (inst->oper == HIROper::BRc || inst->oper == HIROper::BRu)
			{	// `BR` instruction is the end of a BB
				(basic_blocks.end() - 1)->end = iidx;
				flag_in_bb = false;
			}
			else if (inst->oper == HIROper::LABEL)
			{	// `LABEL` is an end of a BB, but also a begin of another BB
				if (last_idx == INVALID_INST_IDX)
					throw std::logic_error("A label is found but last_idx is invalid");
				(basic_blocks.end() - 1)->end = last_idx;
				if (opts.debug_level)
				{	// keep BB info in comments
					inst->cominfo = new std::string("BB: ");
					(*inst->cominfo) += std::to_string(basic_blocks.size());
				}
				basic_blocks.push_back(tempbb);
			}
		}
		else
		{	// a new BB is found
			flag_in_bb = true;
			/*
			 * Fix: if this instruction is `br` (the first instruction
			 * of this BB is `br`), then the instruction itself
			 * forms a new BB!
			 */
			if (inst->oper == HIROper::BRc || inst->oper == HIROper::BRu)
				tempbb.end = iidx, flag_in_bb = false;

			if (opts.debug_level)
			{	// keep BB info in comments
				empty_line.cominfo = new std::string("BB: ");
				(*empty_line.cominfo) += std::to_string(basic_blocks.size());
				if (inst->oper != HIROper::LABEL)
				{	// insert an empty line inst
					insert_inst(empty_line, iidx);
					if (tempbb.end == iidx) ++tempbb.end;
					tempbb.begin = ++iidx;
					++ninst;
				}
				else
				/*
				 * If the instruction is a label, there is no need to
				 * insert an empty line. Just attach the comment info to it.
				 */
					inst->cominfo = empty_line.cominfo;
			}
			basic_blocks.push_back(tempbb);
		}
		last_idx = iidx;
	}
	// End of function reached
	if (flag_in_bb)
	{	// there is still a BB hasnot ended
		//assert(last_idx != INVALID_INST_IDX);
		if (last_idx == INVALID_INST_IDX)
			throw std::logic_error("Still in BB but no non-empty inst");
		(basic_blocks.end() - 1)->end = last_idx;
	}

	// Now, fill `asstemps` array
	if (basic_blocks.at(0).begin == INVALID_INST_IDX)
		bidx = 1u;
	else
		bidx = 0u;
	for (; bidx < basic_blocks.size(); ++bidx)
	{
		auto bb = basic_blocks.begin() + bidx;
		// first, fill the array
		for (iidx = bb->begin; iidx <= bb->end; ++iidx)
		{
			HIRTempno dest = ircode.at(iidx).get_dest();
			if (dest != INVALID_TEMP_NO && bb->asstemps.find(dest) == bb->asstemps.end())
				/*
				 * Record the temp that is assigned in this BB and
				 * map it to the index of the first instruction that assigns it.
				 */
				bb->asstemps[dest] = iidx;
		}
		// then, update the `temps` of the function
		for (auto & temp : bb->asstemps)
		{
			uint32_t fref = temps.at(temp.first).frefed,
				lref = temps.at(temp.first).lrefed;
			if (fref == INVALID_INST_IDX)
			{
				if (lref != INVALID_INST_IDX)
					throw std::logic_error(std::string("temp ") +
						std::to_string(temp.first) + "has invalid `frefed` but `lrefed`" +
						std::to_string(lref));
				temps.at(temp.first).localof = bidx;
			}
			else if (temp.second < fref && lref <= bb->end)
				// the temp is refered only after assigned in this BB
				temps.at(temp.first).localof = bidx;
		}
	}

	// Mark all unused arguments as local of 0 as `frefed` will not be maintained
	for (ta = 0u; ta < nparams; ++ta)
		if (temps.at(ta).frefed == INVALID_INST_IDX)
		{
			if (temps.at(ta).lrefed != INVALID_INST_IDX)
				throw std::logic_error(std::string("temp ") +
					std::to_string(ta) + "has invalid `frefed` but `lrefed`" +
					std::to_string(temps.at(ta).lrefed));
			temps.at(ta).localof = 0u;
		}
	return basic_blocks.size();
}

/*
 * Search the BB whose first instruction is label `label`.
 * Return the BB index of `INVALID_BB_IDX` if not found.
 */
static uint32_t search_bb(const HIRFunct &funct, HIRLabel label)
{
	uint32_t nbb = funct.basic_blocks.size(), i;
	for (i = 1ul; i < nbb; ++i)
	{
		auto begininst = funct.ircode.begin() + funct.basic_blocks.at(i).begin;
		if (begininst->oper == HIROper::LABEL && begininst->labelno == label)
			return i;
	}
	return INVALID_BB_IDX;
}

/*
 * Construct the control flow graph for the function
 * by setting `pred` and `succ` of basic blocks.
 */
void HIRFunct::construct_control_flow_graph()
{
	size_t nbb = basic_blocks.size(), i;

	if (nbb > 0ul)
	{
	// deal with the No.0 BB
		basic_blocks.at(0u).succ.push_back(1u);
		basic_blocks.at(1u).pred.push_back(0u);
	}

	for (i = 1ul; i < nbb; ++i)
	{
		// the last instruction of this BB		
		auto endinst = ircode.begin() + basic_blocks.at(i).end;
		//assert(endinst->oper != HIROper::EMPTY_LINE);
		if (endinst->oper == HIROper::EMPTY_LINE)
			throw std::logic_error(
				std::string("The last instruction of BB ") + std::to_string(i)
				+ " is empty line!"
			);
		if (endinst->oper == HIROper::BRc)
		{
			uint32_t bt1 = search_bb(*this, endinst->iftrue),
				bt2 = search_bb(*this, endinst->iffalse);
			if (bt1 == INVALID_BB_IDX || bt2 == INVALID_BB_IDX)
				throw std::logic_error(
					"failed to find succ of BB" + std::to_string(i));
			basic_blocks.at(i).succ.push_back(bt1);
			basic_blocks.at(bt1).pred.push_back(i);
			basic_blocks.at(i).succ.push_back(bt2);
			basic_blocks.at(bt2).pred.push_back(i);
		}
		else if (endinst->oper == HIROper::BRu)
		{
			uint32_t bt = search_bb(*this, endinst->brdest);
			if (bt == INVALID_BB_IDX)
				throw std::logic_error(
					"failed to find succ of BB" + std::to_string(i));
			basic_blocks.at(i).succ.push_back(bt);
			basic_blocks.at(bt).pred.push_back(i);
		}
		else if (endinst->oper == HIROper::RET)
		{
			if (!basic_blocks.at(i).succ.empty())
				throw std::logic_error(
					"succ of ret BB " + std::to_string(i) + " is not empty");
		}
		else
		{
			/*
			 * The last BB might just contains a redundant label,
			 * so its last instruction might be neither `br` nor `ret`.
			 */
			if (i + 1u < nbb)
			{
				basic_blocks.at(i).succ.push_back(i + 1u);
				basic_blocks.at(i + 1u).pred.push_back(i);
			}
		}	
	}
}

/*
 * Traverse the CFG using DFS and set `reachable` flag.
 */
void HIRFunct::traverse_control_flow_graph(BasicBlock & bb)
{
	bb.reachable = true;
	for (auto suc : bb.succ)
		if (basic_blocks.at(suc).reachable == false)
			traverse_control_flow_graph(basic_blocks.at(suc));
}

/*
 * Scan instructions and do strength reduction, such as:
 * replace some `MUL`(integer) with `SHL`;
 * replace some `DIV`(integer) with `ASHR`;
 * ...
 */
void HIRFunct::opt_strength_reduction()
{
	int i;
	for (auto & inst : ircode)
	{	// scan all instructions
		if (inst.oper == HIROper::MUL)
		{	// for `MUL` instruction
			if (inst.op1.tp == HIROpnd::IMM)
			{
				/*
				 * Check whether the imm value (`inst.op1.imm.ival`)
				 * is power of 2 and replace this instruction with
				 * `SHL`(shift left) or `ADD`.
				 */
				for (i = 0; i < 32; i++)
					if ((1 << i) == inst.op1.imm.ival)
					{
						inst.op1 = inst.op2;
						inst.op2.tp = HIROpnd::IMM;
						inst.op2.imm.ival = i;
						inst.oper = HIROper::SHL;
						break;
					}
			}
			else if (inst.op2.tp == HIROpnd::IMM)
			{
				// Do the same thing for another operand `op2`
				for (i = 0; i < 32; i++)
					if ((1 << i) == inst.op2.imm.ival)
					{
						inst.op2.imm.ival = i;
						inst.oper = HIROper::SHL;
						break;
					}
			}
		}
	}
}

/*
 * Scan instructions and merge adjacent instructions if possible.
 * For example, if we have:
```
64120:	%9 = fadd double %3, %10
64121:	%2 = fadd double %9, 0
```
 * and, `%9` is only used here (both its `frefed` and `lrefed` are 64121),
 * we can replace them with:
```
64120:	%2 = fadd double %3, %10
64121:	<EMPTY_LINE>
```
 */
void HIRFunct::opt_merge_adjacent()
{
	size_t bbidx, i0, i1;
	std::vector<HIRInst>::iterator inst0, inst1;
	HIRTempno dest;

	for (bbidx = 1u; bbidx < basic_blocks.size(); ++bbidx)
		for (i0 = basic_blocks.at(bbidx).begin, i1 = i0 + 1ul,
			inst0 = ircode.begin() + i0, inst1 = inst0 + 1l;
			i1 <= basic_blocks.at(bbidx).end;
			++i0, ++i1, ++inst0, ++inst1)
		{	/*
			 * Access two adjacent instructions in each iteration.
			 * Now `inst1` and `inst2` are the two iterators of the
			 * adjacent instructions, and `i1`, `i2` are their indexes.
			 */
			if ((inst1->oper == HIROper::ADD || inst1->oper == HIROper::FADD) &&
				(inst1->op2.tp == HIROpnd::IMM && inst1->op2.imm.ival == 0l))
			{
			/*
			 * Use `get_dest_of_inst()` to get the destination temp of `*inst1`.
			 * If the got `dest` is valid (not `INVALID_TEMP_NO`), and `inst2->op1.tp`
			 * is also a temp, and its temp number (`op2.temp`) is the same as `dest`,
			 * and it is ONLY USED HERE (use `get_temp_future_use()`):
			 * replace `inst1->dest` with `inst2->dest` and set `inst2` invalid.
			 * NOTE:
			 * As we follow the rule that `fassigned` and `f/lrefed` are NOT
			 * maintained after BBs are divided, there is no need to check them!
			 */
				dest = inst0->get_dest();
				if (dest != INVALID_TEMP_NO
					&& inst1->op1.tp == HIROpnd::TEMP && dest == inst1->op1.temp
					&& temps.at(dest).localof == bbidx
					&& (3ul & get_temp_future_use(dest, i1 + 1u, bbidx)) != 1ul
				)
				{
					temps.at(dest).frefed = INVALID_INST_IDX;
					temps.at(dest).lrefed = INVALID_INST_IDX;
					size_t i;
					if (opts.debug_level != 0 && temps.at(dest).fassigned == i0)
					{
					/*
					 * NOTE:
					 * If temp `dest` is first assigned here, we should scan the instructions
					 * after it to find the next instruction that assigns it.
					 * But now, there is no need to do this actually because of new rule.
					 * So, if debug mode is not enabled, we don't do this.
					 */
						temps.at(dest).fassigned = INVALID_INST_IDX;
						for (i = i0 + 1u; i <= basic_blocks.at(bbidx).end; ++i)
							if (ircode.at(i).get_dest() == dest)
							{
								temps.at(dest).fassigned = i;
								break;
							}
					}
					if (opts.debug_level != 0 && temps.at(inst1->dest).fassigned == i1)
						temps.at(inst1->dest).fassigned = i0;
					inst0->dest = inst1->dest;
					inst1->oper = HIROper::EMPTY_LINE;
					if (inst1->cominfo != nullptr)
					{	// as `inst2` is `ADD` or `FADD` (not `CALL`), its `cominfo` is safe
						if (inst0->cominfo == nullptr)
						{	// just move
							inst0->cominfo = inst1->cominfo;
							inst1->cominfo = nullptr;
						}
						else
						{	// concatate
							*inst0->cominfo += "; " + *inst1->cominfo;
							delete inst1->cominfo;
						}
					}
				}
			}
		}
}

// Don't use these flags of temp!
#define fassigned ERROR
#define frefed ERROR
#define lrefed ERROR

/*
 * Local DCE: Eliminate local (in a BB) dead code.
 * If flow equations for live temps have been solved,
 * please set `use_live_temps` is `true`, so that the solution
 * (`live_temps_o`) will be used.
 * Otherwise, it will assume that all non-local temps
 * are live at the exit of a BB.
 * Return the number of instructions that are eliminated.
 */
size_t HIRFunct::opt_dead_code_elimination(bool use_live_temps)
{
	std::vector<BasicBlock>::iterator bb;
	HIRTempno dest;
	std::vector<HIRTempno> srctemps;
	size_t elim_ymr = 0ul;

	for (bb = basic_blocks.begin() + 1l; bb != basic_blocks.end(); ++bb)
	{
		uint32_t iidx = bb->end;
		bool flag_eliminated = false;
		if (use_live_temps)
		{	// Set all temps that are live at the exit as live
			for (auto & temp : temps)
				temp.live = false;
			for (auto tempno : bb->livevar_out)
				temps.at(tempno).live = true;
		}
		else
			// Assume that all non-local temps are live
			for (auto & temp : temps)
				if (temp.localof == INVALID_BB_IDX)
					temp.live = true;
				else
					temp.live = false;
		++iidx;
		while (iidx-- > bb->begin)
		{
			if (ircode.at(iidx).oper == HIROper::EMPTY_LINE
				|| ircode.at(iidx).oper == HIROper::LABEL)
				continue;
			dest = ircode.at(iidx).get_dest();
			/*
			 * `dest` being invalid means that it is a `STORE`
			 * or `CALL` instruction. It should not be eliminated,
			 * but its operand temps should be set as live!
			 */
			if (dest == INVALID_TEMP_NO || temps.at(dest).live)
			{
				if (dest != INVALID_TEMP_NO)
					temps.at(dest).live = false;
				ircode.at(iidx).get_srctemps(srctemps);
				for (auto st : srctemps)
					temps.at(st).live = true;
			}
			else if (dest != INVALID_TEMP_NO)
			{	// dead code found
				++elim_ymr;
				flag_eliminated = true;
				if (ircode.at(iidx).oper == HIROper::CALL)
				{
					ircode.at(iidx).dest = INVALID_TEMP_NO;
					// Set arguments of the `CALL` live
					ircode.at(iidx).get_srctemps(srctemps);
					for (auto st : srctemps)
						temps.at(st).live = true;
				}
				else
					ircode.at(iidx).oper = HIROper::EMPTY_LINE;
			}
		}
		if (flag_eliminated)
		{	// Update `asstemps` array!
			uint32_t iidx;
			bb->asstemps.clear();
			for (iidx = bb->begin; iidx <= bb->end; ++iidx)
			{
				HIRTempno dest = ircode.at(iidx).get_dest();
				if (dest != INVALID_TEMP_NO &&
					bb->asstemps.find(dest) == bb->asstemps.end())
					bb->asstemps[dest] = iidx;
			}
		}
	}
	return elim_ymr;
}

/*
 * Local CSE: Eliminate local common subexpressions.
 * If flow equations for live temps have been solved,
 * please set `use_live_temps` is `true`, so that the solution
 * (`live_temps_o`) will be used.
 * Otherwise, it will assume that all non-local temps
 * are live at the exit of a BB.
 * Return the number of CSE eliminated.
 */
size_t HIRFunct::opt_common_subexpr_elimination(bool use_live_temps)
{
	std::vector<BasicBlock>::const_iterator bb;
	HIRTempno dest;		// dest temp of the current instruction
	HIRTempno desti;	// dest temp of the scanning instruction
	uint32_t iidx;
	uint32_t ib, iw;	// indexes for backward and forward
	std::vector<HIRTempno> srctemps;// source temps of the current inst
	size_t elim_ymr = 0ul;

	for (bb = basic_blocks.begin() + 1l; bb != basic_blocks.end(); ++bb)
	{
		for (iidx = bb->begin + 1u; iidx <= bb->end; ++iidx)
		{
			if ((dest = ircode.at(iidx).get_dest()) == INVALID_TEMP_NO)
				continue;
			ircode.at(iidx).get_srctemps(srctemps);
			ib = iidx;
			while (ib-- > bb->begin)
			{
			/*
			 * Scan the instructions backward to find
			 * common subexpressions.
			 */
				if ((desti = ircode.at(ib).get_dest()) == INVALID_TEMP_NO)
					continue;
				if (std::find(srctemps.begin(), srctemps.end(), desti)
					!= srctemps.end())
					/*
					 * If one of the source temps of the `iidx`-th inst
					 * is assigned, stop the scanning!
					 */
					break;
				if (ircode.at(ib).oper != HIROper::LOAD
					&& ircode.at(ib).oper != HIROper::STORE
					&& ircode.at(iidx).opequals(ircode.at(ib)))
				{	// Same operation is found!
					if ((use_live_temps && bb->livevar_out.count(dest) > 0ul)
						|| (!use_live_temps && temps.at(dest).localof == INVALID_BB_IDX))
					/*
					 * If the dest temp is live at the end of this BB,
					 * it will be kept by just replacing the inst with an `ADD`/`FADD`.
					 * If `use_live_temps` is `false`, all non-local temps will be
					 * considered live!
					 */
					{
						if (temps.at(dest).type == HIRBtype::DOUBLE
							|| temps.at(dest).type == HIRBtype::FLOAT)
							ircode.at(iidx).oper = HIROper::FADD;
						else
							ircode.at(iidx).oper = HIROper::ADD;
						ircode.at(iidx).op1.tp = HIROpnd::TEMP;
						ircode.at(iidx).op1.temp = desti;
						ircode.at(iidx).op2.tp = HIROpnd::IMM;
						ircode.at(iidx).op2.imm.ival = 0l;
					}
					else
					{	// Delete the instruction
						ircode.at(iidx).oper = HIROper::EMPTY_LINE;
						// Replace `dest` with `desti` in the following instructions--
						for (iw = iidx + 1u; iw <= bb->end; ++iw)
						{
							ircode.at(iw).srctemps_replace(dest, desti);
							if (ircode.at(iw).get_dest() == dest)
							// until `dest` is assigned again
								break;
						}
					}
					++elim_ymr;
				}
			}
		}
	}
	return elim_ymr;
}
